package Offer.q51_reversePairs;

public class Solution_1 {
    int[] nums, tmp;
    /*
    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
    输入一个数组，求出这个数组中的逆序对的总数
    这里用的归并排序模版 加一行代码即可解决
    另一个方法为树状数组
    此题与leetcode315强相关 其为：计算右侧小于当前元素的个数
     */
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int mid = (l + r) >> 1;
        int res = mergeSort(l, mid) + mergeSort(mid + 1, r);
        // 合并阶段
        int i = l, j = mid + 1;
        int cnt = 0;

        while(i <= mid && j <= r){// 在范围之内
            if(nums[i] <= nums[j]){
                tmp[cnt++] = nums[i++];
            }else{
                res += (mid - i + 1);// 只需要这行代码
                /*
                当前左指针大于右指针指向数值,
                因此left部分中mid - left + 1部分(即left部分中的后半部分)肯定都比右指针大,
                而他们在原数组中都是在右指针的前面的, 所以每个数都构成一个逆序对。
                 */
                tmp[cnt++] = nums[j++];
            }
        }

        while (i <= mid){// 右边遍历结束   左边还剩
            tmp[cnt++] = nums[i++];
        }
        while(j <= r){// 左边遍历结束   右边还剩
            tmp[cnt++] = nums[j++];
        }

        // 将temp中的元素  全部都copy到原数组里边去
        for (int k = 0; k < r - l + 1; ++k) {
            nums[k + l] = tmp[k];
        }
        return res;
    }
}
